package org.jojo.sort;

import java.util.Arrays;

/**
 * @author xiexiong
 * 堆排序
 * 最大堆：所有的父节点都比它的子节点的值要大
 * 构建最大堆：递归堆化
 * 已知子节点index，父节点的index 为 (sunIndex -1)/2
 * 已经父节点index, 左儿子的index为 2*parentIndex+1  右儿子的index为 2*parentIndex+2
 *
 *
 */
public class HeapSort {

    public static void heapSort(int[] arr) {
        buildHeap(arr,arr.length);
        int length = arr.length - 1;
        for (int i = length; i >= 0; i--) {
            swap(arr, i, 0);
            heapify(arr, i, 0);
        }
    }

    public static void buildHeap(int[] arr,int length) {
        int lastNode = length - 1;
        int heapLength = (lastNode - 1) / 2;
        for (int i = heapLength; i >= 0; i--) {
            heapify(arr, length, i);
        }
    }

    public static void heapify(int[] arr, int length, int index) {
        if (index >= length) {
            return;
        }
        int c1 = index * 2 + 1;
        int c2 = index * 2 + 2;
        int max = index;
        if (c1 < length && arr[c1] < arr[max]) {
            max = c1;
        }
        if (c2 < length && arr[c2] < arr[max]) {
            max = c2;
        }
        if (max != index) {
            swap(arr, max, index);
            heapify(arr, length, max);
        }
    }

    public static void swap(int[] arr, int max, int index) {
        int temp = arr[max];
        arr[max] = arr[index];
        arr[index] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 10, 3, 5, 1, 2};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}
